#include "shop.h"
#include <bits/stdc++.h>

using namespace std;

int n,k;
int tmp[2][2];
vector<int>lef;

bool q(int x,int y,int z){
	tmp[0][0] = x,tmp[1][0] = y;tmp[1][1] = z;
	return query(tmp[0],1,tmp[1],2);
}

bool q(int x,int y){
	tmp[0][0] = x;tmp[1][0] = y;return query(tmp[0],1,tmp[1],1);
}

void ins(int y){
	int pos = 0,l = 0,r = (int)lef.size() - 1;
	while(l <= r){
		int mid = l+r>>1;
		if(q(y,lef[mid])) r = mid - 1,pos = mid;
		else l = mid+1;
	}
	lef.insert(lef.begin()+pos,y);
}

void find_price(int tp,int _n,int _k,int ans[]){
	n = _n,k = _k;
	lef.resize(0);
	if(n == 1){ans[0] = 1;return;}
	if(n <= 2 || tp == 3){
		lef.resize(n); for(int i = 0;i < n;i++) lef[i] = i;
		if(!q(lef[0],lef[n-1])) reverse(lef.begin(),lef.end());
	}else{
		int x,y = 0,a = 1;lef.push_back(a);
		for(int i = 2;i < n;i++){
			x = i;
			if(!q(x,y)) swap(x,y);
			if(q(a,x,y)) lef.push_back(a=y),y = x;
		}
		ins(y);
	}
	int l = 0,r = (int)lef.size() - 2,pos = (int)lef.size() - 1;
	while(l <= r){
		int mid = l+r>>1;
		if(!q(lef.back(),lef[mid],lef[mid+1])) l = mid+1;
		else pos = mid,r = mid-1;
	}
	for(int i = 0;i < pos;i++) ans[lef[i]] = 0;
	ans[lef[pos]] = ((int)lef.size() - pos - 1 - k) & 1; for(int i = pos + 1;i < lef.size();i++) ans[lef[i]] = 1;
}
